package daily.oct;

import java.util.*;

public class lc417 {
    /*
    主要思路，逆向思维
    从边界开始，逆流而上（新位置高度 >= 当前位置高度）
    标记所有可达的位置
    最后找出两个海洋都能到达的单元格
     */
    private static final int[][] DIRECTIONS = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        List<List<Integer>> result = new ArrayList<>();
        if (heights == null || heights.length == 0 || heights[0].length == 0) {
            return result;
        }

        int m = heights.length;
        int n = heights[0].length;

        // 创建两个布尔矩阵来标记能到达太平洋和大西洋的单元格
        boolean[][] canReachPacific = new boolean[m][n];
        boolean[][] canReachAtlantic = new boolean[m][n];

        // 创建两个队列用于 BFS
        Queue<int[]> pacificQueue = new LinkedList<>();
        Queue<int[]> atlanticQueue = new LinkedList<>();

        // 初始化太平洋边界（第一列和第一行）
        for (int i = 0; i < m; i++) {
            pacificQueue.offer(new int[]{i, 0});
            canReachPacific[i][0] = true;
        }
        for (int j = 1; j < n; j++) {
            pacificQueue.offer(new int[]{0, j});
            canReachPacific[0][j] = true;
        }

        // 初始化大西洋边界（最后一列和最后一行）
        for (int i = 0; i < m; i++) {
            atlanticQueue.offer(new int[]{i, n - 1});
            canReachAtlantic[i][n - 1] = true;
        }
        for (int j = 0; j < n - 1; j++) {
            atlanticQueue.offer(new int[]{m - 1, j});
            canReachAtlantic[m - 1][j] = true;
        }

        // BFS 遍历太平洋
        bfs(heights, pacificQueue, canReachPacific);

        // BFS 遍历大西洋
        bfs(heights, atlanticQueue, canReachAtlantic);

        // 收集同时能到达两个海洋的单元格
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (canReachPacific[i][j] && canReachAtlantic[i][j]) {
                    result.add(Arrays.asList(i, j));
                }
            }
        }
        return result;
    }

    private void bfs(int[][] heights, Queue<int[]> queue, boolean[][] canReach) {
        int m = heights.length;
        int n = heights[0].length;

        while (!queue.isEmpty()) {
            int[] cell = queue.poll();
            int x = cell[0];
            int y = cell[1];

            for (int[] dir : DIRECTIONS) {
                int nx = x + dir[0];
                int ny = y + dir[1];

                // 检查新坐标是否在矩阵范围内
                if (nx >= 0 && nx < m && ny >= 0 && ny < n) {
                    // 检查是否未被访问过且高度满足逆流条件（新位置高度 >= 当前位置高度）
                    if (!canReach[nx][ny] && heights[nx][ny] >= heights[x][y]) {
                        canReach[nx][ny] = true;
                        queue.offer(new int[]{nx, ny});
                    }
                }
            }
        }
    }
}
